{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Substring with At Most Two Distinct Characters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: lengthOfLongestSubstringTwoDistinct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #至多包含两个不同字符的最长子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "给你一个字符串 <code>s</code> ，请你找出&nbsp;<strong>至多&nbsp;</strong>包含 <strong>两个不同字符</strong> 的最长子串，并返回该子串的长度。\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"eceba\"\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>满足题目要求的子串是 \"ece\" ，长度为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"ccaabbb\"\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>满足题目要求的子串是 \"aabbb\" ，长度为 5 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 由英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-substring-with-at-most-two-distinct-characters](https://leetcode.cn/problems/longest-substring-with-at-most-two-distinct-characters/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-substring-with-at-most-two-distinct-characters](https://leetcode.cn/problems/longest-substring-with-at-most-two-distinct-characters/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"eceba\"', '\"ccaabbb\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if len(s)==1:\n",
    "            return 1\n",
    "        slow = 0\n",
    "        fast = 1\n",
    "        max_len = 2\n",
    "        res = ''\n",
    "        while fast<len(s)-1:\n",
    "            fast+=1\n",
    "            if len(set(s[slow:fast+1]))>2:\n",
    "                for i in range(slow+1,fast+1):\n",
    "                    if len(set(s[i:fast+1]))==2:\n",
    "                        slow = i\n",
    "                        break\n",
    "            if fast-slow+1>max_len:\n",
    "                res = s[slow:fast+1]\n",
    "                max_len = fast-slow+1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n < 3:\n",
    "            return n\n",
    "\n",
    "        left,right = 0,0\n",
    "        hashmap = defaultdict()\n",
    "        max_len = 2\n",
    "\n",
    "        while right < n:\n",
    "            hashmap[s[right]] = right\n",
    "            right += 1\n",
    "\n",
    "            if len(hashmap) == 3:\n",
    "                del_idx = min(hashmap.values())\n",
    "                del hashmap[s[del_idx]]\n",
    "                left = del_idx + 1\n",
    "\n",
    "            max_len = max(max_len, right - left)\n",
    "\n",
    "        return max_len\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        #至少包含两个不同字符最大子串长度值\n",
    "        right,left=0,0\n",
    "        max_s,temp_s=0,0\n",
    "        hashmap=Counter()\n",
    "        for right,x in enumerate(s):\n",
    "            hashmap[x]+=1\n",
    "            if len(hashmap) ==2:\n",
    "                #哈希表长度为2的时候表明只有两个不同字符，更新max\n",
    "                max_s=max(max_s, right-left+1)\n",
    "            while len(hashmap)>2:\n",
    "                #哈希表中有三个不同字符的时候,删除最左边元素直至长度为2\n",
    "                head=s[left]\n",
    "                hashmap[head]-=1\n",
    "                if hashmap[head]==0:\n",
    "                    del hashmap[head]\n",
    "                left+=1\n",
    "            max_s=max(max_s, right-left+1)\n",
    "        return max_s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        r = l = res = 0\n",
    "        while r < len(s):\n",
    "            if len(set(s[l:r+1])) >= 3 :\n",
    "                l += 1\n",
    "        \n",
    "            r += 1\n",
    "        return r-l\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        vis = set()\n",
    "        cnt = [0 for _ in range(100)]\n",
    "        q = deque()\n",
    "        j = 0\n",
    "        ans = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if not cnt[ord(c) - ord('a')]:\n",
    "                vis.add(c)\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "            while len(vis) > 2:\n",
    "                cnt[ord(s[j]) - ord('a')] -= 1\n",
    "                if not cnt[ord(s[j]) - ord('a')]:\n",
    "                    vis.remove(s[j])\n",
    "                j += 1\n",
    "            ans = max(ans, i - j + 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        left_index=0\n",
    "        right_index=0\n",
    "        max_lens=0\n",
    "        child_string=\"\"\n",
    "        for index in range(len(s)):\n",
    "            child_string+=s[index]\n",
    "            while(len(set(child_string))>2):\n",
    "                child_string=s[left_index:right_index+1]\n",
    "                left_index+=1\n",
    "            if len(child_string)>max_lens:\n",
    "                max_lens=len(child_string)\n",
    "            right_index+=1\n",
    "        return max_lens\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        max_len, hash_map = 0, {}\n",
    "\n",
    "        start = 0\n",
    "        for end in range(len(s)):\n",
    "            hash_map[s[end]] = hash_map.get(s[end], 0) + 1\n",
    "            if len(hash_map) <= 2:\n",
    "                max_len = max(max_len, end - start + 1)\n",
    "\n",
    "            while len(hash_map) > 2:\n",
    "                head = s[start]\n",
    "                hash_map[head] -= 1\n",
    "                if hash_map[head] == 0:\n",
    "                    del hash_map[head]\n",
    "                start += 1\n",
    "            \n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        # self\n",
    "        n = len(s)\n",
    "        # freq = [0] * 26\n",
    "        import collections\n",
    "        freq = {}\n",
    "        left = right = 0\n",
    "        res = 0\n",
    "        while right < n:\n",
    "            r = s[right]\n",
    "            if r not in freq:\n",
    "                freq[r] = 1\n",
    "            else:\n",
    "                freq[r] += 1\n",
    "            if len(freq) > 2:\n",
    "                res = max(res, right - left)\n",
    "                while len(freq) > 2:\n",
    "                    l = s[left]\n",
    "                    freq[l] -= 1\n",
    "                    if freq[l] == 0:\n",
    "                        del freq[l]\n",
    "                    left += 1\n",
    "            right += 1\n",
    "        res = max(res, right - left)\n",
    "        return res\n",
    "\n",
    "        # # self - AC!\n",
    "        # n = len(s)\n",
    "        # # freq = [0] * 26\n",
    "        # import collections\n",
    "        # freq = collections.defaultdict(int)\n",
    "        # left = right = 0\n",
    "        # chars = 0\n",
    "        # res = 0\n",
    "        # while right < n:\n",
    "        #     r = s[right]\n",
    "        #     if freq[r] == 0:\n",
    "        #         chars += 1\n",
    "        #     freq[r] += 1\n",
    "        #     if chars > 2:\n",
    "        #         print(s[left:right])\n",
    "        #         res = max(res, right - left)\n",
    "        #         while chars > 2:\n",
    "        #             l = s[left]\n",
    "        #             freq[l] -= 1\n",
    "        #             if freq[l] == 0:\n",
    "        #                 chars -= 1\n",
    "        #             left += 1\n",
    "        #     right += 1\n",
    "        # res = max(res, right - left)\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        idx1 = 0\n",
    "        idx2 = 0\n",
    "        cnter  = defaultdict(int)\n",
    "        cnter[s[idx1]] += 1\n",
    "        ret_len = 1\n",
    "    \n",
    "        while idx1 <= idx2 and idx2 < len(s):\n",
    "            while idx2 < len(s) and len(cnter) <= 2:\n",
    "                if ret_len < idx2 - idx1 + 1:\n",
    "                    ret_len = idx2 - idx1 + 1\n",
    "                idx2 += 1\n",
    "                if idx2 < len(s):\n",
    "                    cnter[s[idx2]] += 1\n",
    "            while idx1 <= idx2 and len(cnter) > 2:\n",
    "                cnter[s[idx1]] -= 1\n",
    "                if cnter[s[idx1]] == 0:\n",
    "                    cnter.pop(s[idx1])\n",
    "                idx1 += 1\n",
    "        \n",
    "        return ret_len\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        N = len(s)\n",
    "        if N < 3:\n",
    "            return N\n",
    "\n",
    "        left, right = 0, 0\n",
    "        res = 2\n",
    "        hash_map = defaultdict()\n",
    "\n",
    "        while right < N:\n",
    "            hash_map[s[right]] = right\n",
    "            while len(hash_map) > 2:\n",
    "                del_index = min(hash_map.values())\n",
    "                del hash_map[s[del_index]]\n",
    "                left = del_index + 1\n",
    "            res = max(res, right - left + 1)\n",
    "            right += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution():\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        hash_s = defaultdict(int)\n",
    "        max_len = 0\n",
    "        left = 0\n",
    "        for right in range(len(s)):\n",
    "            hash_s[s[right]] += 1\n",
    "            if len(hash_s) <= 2:\n",
    "                max_len = max(max_len, right - left + 1)\n",
    "            # print(left, right, hash_s, len(hash_s))\n",
    "\n",
    "            if len(hash_s) > 2:\n",
    "                hash_s[s[left]] -= 1\n",
    "                if hash_s[s[left]] == 0:\n",
    "                    del hash_s[s[left]]\n",
    "                left += 1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        res = 0\n",
    "        left = 0\n",
    "        dic = collections.defaultdict(int)\n",
    "        for right, ch in enumerate(s):\n",
    "            dic[ch] += 1\n",
    "            while len(dic) > 2:\n",
    "                dic[s[left]] -= 1\n",
    "                if dic[s[left]] == 0:\n",
    "                    del dic[s[left]]\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ？\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        from collections import defaultdict\n",
    "        win = defaultdict(int) # 窗口为字典,key为字母，value为他在窗口出现的次数\n",
    "        left = 0\n",
    "        right = 0\n",
    "        maxLen = 0\n",
    "        curLen = 0\n",
    "        cnt = 0  # 窗口内有几种不同元素\n",
    "        while right < len(s):\n",
    "            if win[s[right]] == 0: # 如果当前元素不存在于窗口\n",
    "                cnt += 1\n",
    "            win[s[right]] += 1\n",
    "            right += 1 # 移动右边界\n",
    "            while cnt>2: # 如果滑动窗口内元素种类大于2，移动左边界\n",
    "                if win[s[left]] == 1: \n",
    "                # 直到移动到一个独特元素，也就是s[left]被移出后，cnt会变化\n",
    "                    cnt -= 1\n",
    "                win[s[left]] -= 1\n",
    "                left += 1\n",
    "            maxLen = max(maxLen,right-left)\n",
    "        return maxLen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        cnt = {}\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        for r in range(len(s)):\n",
    "            if s[r] in cnt:\n",
    "                cnt[s[r]] += 1\n",
    "            else:\n",
    "                cnt[s[r]] = 1\n",
    "            while len(cnt) > 2:\n",
    "                cnt[s[l]] -= 1\n",
    "                if cnt[s[l]] == 0:\n",
    "                    del cnt[s[l]]\n",
    "                l += 1\n",
    "            ans = max(ans, r - l + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n < 3:\n",
    "            return n\n",
    "        winfreq = {}\n",
    "        for c in s:\n",
    "            winfreq[c] = 0\n",
    "        \n",
    "        left, right = 0, 0\n",
    "        res = 2\n",
    "        count = 0\n",
    "        while right < n:\n",
    "            winfreq[s[right]] += 1\n",
    "            if winfreq[s[right]] == 1:\n",
    "                count += 1\n",
    "            right += 1\n",
    "            while count == 3:\n",
    "                winfreq[s[left]] -= 1\n",
    "                if winfreq[s[left]] == 0:\n",
    "                    count -= 1\n",
    "                left += 1\n",
    "            res = max(res, (right-left))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if not s: return 0\n",
    "        if len(s)<3: return len(s)\n",
    "        # 判断值\n",
    "        max_len = 0\n",
    "        queue = []\n",
    "     \n",
    "        for char in s:\n",
    "            queue.append(char)\n",
    "            while len(set(queue))>2: # 滑动条件\n",
    "                del queue[0]\n",
    "            \n",
    "            max_len = max(max_len, len(queue))  # 直接把hashmap里面的value加起来，就是max_le\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if len(s) < 3: return len(s)\n",
    "        ans = 2\n",
    "        left, right = 0, 0\n",
    "        dic = {}\n",
    "        while right < len(s):\n",
    "            dic[s[right]] = right\n",
    "            right += 1\n",
    "            if len(dic) >= 3:\n",
    "                # key = min(dic, key=dic.get)\n",
    "                # left = dic[key]+1\n",
    "                # del dic[key]\n",
    "                del_idx = min(dic.values())\n",
    "                del dic[s[del_idx]]\n",
    "                left = del_idx + 1\n",
    "            ans = max(ans, right-left)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter \n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        \"\"\" Sliding Window \"\"\"\n",
    "\n",
    "        left, right = 0, 0 \n",
    "        n = len(s) \n",
    "        ans = 0 \n",
    "\n",
    "        while right < n:\n",
    "            # print(len(list(Counter(s[left:right]))))\n",
    "            while left < right and len(list(Counter(s[left:right+1]))) > 2:\n",
    "                left += 1 \n",
    "\n",
    "            # if len(list(Counter(s[left:right+1]))) <= 2:\n",
    "            ans = max(ans, right-left+1)\n",
    "            right += 1 \n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if len(s)<=2:\n",
    "            return len(s)\n",
    "        hashs=set()\n",
    "        maxlength=0\n",
    "        for i in range(len(s)-1):\n",
    "            hashs.add(s[i])\n",
    "            for j in range(i,len(s)):\n",
    "                if s[j] not in hashs:\n",
    "                \thashs.add(s[j])\n",
    "                if len(hashs)>2:\n",
    "                    hashs.clear()\n",
    "                    break\n",
    "                maxlength=max(j-i+1,maxlength)\n",
    "        return maxlength\n",
    "                \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        mp = dict()\n",
    "        vis = set()\n",
    "        j = 0\n",
    "        ans = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c not in mp or not mp[c]:\n",
    "                mp[c] = 1\n",
    "                vis.add(c)\n",
    "            else:\n",
    "                mp[c] += 1\n",
    "            while len(vis) > 2:\n",
    "                mp[s[j]] -= 1\n",
    "                if not mp[s[j]]:\n",
    "                    vis.remove(s[j])\n",
    "                j += 1\n",
    "            ans = max(ans, i - j + 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        def get_char_with_the_min_index(index_dict):\n",
    "            min_index = min(index_dict.values())\n",
    "            for k, v in index_dict.items():\n",
    "                if v == min_index:\n",
    "                    return k, v\n",
    "\n",
    "        max_len = 0\n",
    "        cache = {}\n",
    "        start_index = 0\n",
    "        for cur_index, cur_char in enumerate(s):\n",
    "            cache[cur_char] = cur_index\n",
    "            if len(cache.keys()) > 2:\n",
    "                max_len = max(max_len, cur_index - start_index)\n",
    "                popped_char, popped_index = get_char_with_the_min_index(cache)\n",
    "                start_index = popped_index + 1\n",
    "                del cache[popped_char]\n",
    "\n",
    "        max_len = max(max_len, len(s) - start_index)\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        ans=0\n",
    "        cnt=dict()\n",
    "        i,j,n=0,0,len(s)\n",
    "        while j<n:\n",
    "            if s[j] not in cnt:\n",
    "                cnt[s[j]]=1\n",
    "            else:\n",
    "                cnt[s[j]]+=1\n",
    "            while len(cnt)>2:\n",
    "                cnt[s[i]]-=1\n",
    "                if cnt[s[i]]==0:\n",
    "                    del cnt[s[i]]\n",
    "                i+=1\n",
    "            ans=max(ans,j-i+1)\n",
    "            j+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        count = Counter()\n",
    "\n",
    "        for right,c in enumerate(s):\n",
    "            count[c] += 1\n",
    "\n",
    "            while len(count) > 2 and left <= right:\n",
    "                count[s[left]] -= 1\n",
    "                if count[s[left]] == 0:\n",
    "                    del count[s[left]]\n",
    "                left += 1\n",
    "            \n",
    "            ans = max(ans, right-left+1)\n",
    "        return ans if ans > 0 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        left = 0\n",
    "        max_count = 0\n",
    "        record = {}\n",
    "        for i in range(len(s)):\n",
    "            record[s[i]] = i\n",
    "            if len(record)>2:\n",
    "                max_count = max(max_count, i-left)\n",
    "                left = min(record.values())+1\n",
    "                tmp = None\n",
    "                for k in record:\n",
    "                    if record[k] == left-1:\n",
    "                        tmp = k\n",
    "                        break\n",
    "                record.pop(tmp)\n",
    "        max_count = max(max_count, max(record.values())-left+1)\n",
    "        return max_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        if n < 3:\n",
    "            return n\n",
    "\n",
    "        left, right = 0, 0\n",
    "        hashmap = {}\n",
    "        max_len = 2\n",
    "\n",
    "        while right < n:\n",
    "            if len(hashmap) < 3:\n",
    "                hashmap[s[right]] = right\n",
    "                right += 1\n",
    "\n",
    "            if len(hashmap) == 3:\n",
    "                del_idx = min(hashmap.values())\n",
    "                del hashmap[s[del_idx]]\n",
    "                left = del_idx + 1\n",
    "\n",
    "            max_len = max(max_len, right - left)\n",
    "            \n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 要解决这个问题，我们仍然可以使用滑动窗口的方法。与之前的问题稍有不同的是，这次我们允许窗口内有最多两个不同的字符。\n",
    "\n",
    "# 我们可以使用一个字典来存储窗口内每个字符的出现次数。这样，当窗口内的不同字符数量超过2时，我们可以移动窗口的左边界并相应地更新字典，直到窗口内的不同字符数量小于或等于2为止\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        # 初始化窗口的起始和结束位置\n",
    "        start = 0\n",
    "        end = 0\n",
    "        # 初始化最大长度\n",
    "        max_len = 0\n",
    "        # 使用字典来存储窗口内每个字符的出现次数\n",
    "        char_count = {}\n",
    "        \n",
    "        while end < len(s):\n",
    "            # 当前考虑的字符\n",
    "            current_char = s[end]\n",
    "            # 更新字符的出现次数\n",
    "            char_count[current_char] = char_count.get(current_char, 0) + 1\n",
    "            # 扩大窗口\n",
    "            end += 1\n",
    "            \n",
    "            # 当窗口内的不同字符数量超过2时\n",
    "            while len(char_count) > 2:\n",
    "                # 移除最左边的字符，并相应地更新字典\n",
    "                left_char = s[start]\n",
    "                char_count[left_char] -= 1\n",
    "                if char_count[left_char] == 0:\n",
    "                    del char_count[left_char]\n",
    "                start += 1\n",
    "            \n",
    "            # 更新最大长度\n",
    "            max_len = max(max_len, end - start)\n",
    "        \n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        hashtab = dict()\n",
    "        left, right = 0, 0\n",
    "        max_len = 0\n",
    "        while right < len(s):\n",
    "            if s[right] in hashtab:\n",
    "                hashtab[s[right]] += 1\n",
    "            else:\n",
    "                hashtab[s[right]] = 1\n",
    "            if len(hashtab.keys()) <= 2:\n",
    "                max_len = max(max_len, right - left + 1)\n",
    "            else:\n",
    "                if hashtab[s[left]] > 1:\n",
    "                    hashtab[s[left]] -= 1\n",
    "                else:\n",
    "                    del hashtab[s[left]]\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        d, res, l = defaultdict(int), 0, 0\n",
    "        for r, c in enumerate(s):\n",
    "            d[c] += 1\n",
    "            while len(d) > 2:\n",
    "                d[s[l]] -= 1\n",
    "                if d[s[l]] == 0:\n",
    "                    d.pop(s[l])\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        # s consists of English letters. -> bucket \n",
    "        # longest\n",
    "        # two distinct  -> label for bound to move \n",
    "\n",
    "        res = 0\n",
    "        cnt = 0\n",
    "        left = 0\n",
    "        visited = {}\n",
    "        for i in range(len(s)):\n",
    "            visited.setdefault(s[i],0)\n",
    "            if visited[s[i]] == 0:\n",
    "                cnt += 1 \n",
    "            visited[s[i]] += 1\n",
    "            while cnt > 2 and left < i:\n",
    "                visited[s[left]] -= 1\n",
    "                if visited[s[left]] == 0:\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "\n",
    "            #print(left,i,visited,cnt)\n",
    "            \n",
    "            res = max(res,i - left + 1)\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "   def lengthOfLongestSubstringTwoDistinct(self, s: 'str') -> 'int':\n",
    "       n = len(s)\n",
    "       if n < 3:\n",
    "           return n\n",
    "\n",
    "       # 滑动窗口的左右指针\n",
    "       left, right = 0, 0\n",
    "       # hashmap 中的字符 -> 它在滑动窗口中最靠右的位置\n",
    "       hashmap = defaultdict()\n",
    "\n",
    "       max_len = 2\n",
    "\n",
    "       while right < n:\n",
    "           # 当滑动窗口包含小于 3 个字符\n",
    "           hashmap[s[right]] = right\n",
    "           right += 1\n",
    "\n",
    "           # 滑动窗口包含 3 个字符\n",
    "           if len(hashmap) == 3:\n",
    "               # 删除最左边的字符\n",
    "               del_idx = min(hashmap.values())\n",
    "               del hashmap[s[del_idx]]\n",
    "               # 删除滑动窗口的左指针\n",
    "               left = del_idx + 1\n",
    "\n",
    "           max_len = max(max_len, right - left)\n",
    "\n",
    "       return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        if l < 3:\n",
    "            return l\n",
    "        \n",
    "        hashmap = {}\n",
    "        left = 0\n",
    "        right = 0\n",
    "        maxlen = 2\n",
    "        while right < l:\n",
    "            hashmap[s[right]] = right\n",
    "            right += 1\n",
    "\n",
    "            if len(hashmap) == 3:\n",
    "                idx = min(hashmap.values())\n",
    "                del hashmap[s[idx]]\n",
    "                left = idx + 1\n",
    "            \n",
    "            maxlen = max(maxlen, right - left)\n",
    "        return maxlen\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        vis = set()\n",
    "        cnt = [0 for _ in range(100)]\n",
    "        q = deque()\n",
    "        j = 0\n",
    "        ans = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if not cnt[ord(c) - ord('a')]:\n",
    "                vis.add(c)\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "            while len(vis) > 2:\n",
    "                cnt[ord(s[j]) - ord('a')] -= 1\n",
    "                if not cnt[ord(s[j]) - ord('a')]:\n",
    "                    vis.remove(s[j])\n",
    "                j += 1\n",
    "            ans = max(ans, i - j + 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        res = 0\n",
    "        n = len(s)\n",
    "        cache = {}\n",
    "        left = 0\n",
    "        for i in range(n):\n",
    "            c = s[i]\n",
    "            cache[c] = cache.get(c, 0) + 1\n",
    "            while len(cache) > 2:\n",
    "                cache[s[left]] -= 1\n",
    "                if cache[s[left]] == 0:\n",
    "                    del cache[s[left]]\n",
    "                left += 1\n",
    "            res = max(res, i - left + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        r = l = res = 0\n",
    "        while r < len(s):\n",
    "            if len(set(s[l:r+1])) >= 3 :\n",
    "                l += 1\n",
    "            res = max(res , r - l + 1)\n",
    "            r += 1\n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        vis = set()\n",
    "        cnt = [0 for _ in range(100)]\n",
    "        q = deque()\n",
    "        j = 0\n",
    "        ans = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if not cnt[ord(c) - ord('a')]:\n",
    "                vis.add(c)\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "            while len(vis) > 2:\n",
    "                cnt[ord(s[j]) - ord('a')] -= 1\n",
    "                if not cnt[ord(s[j]) - ord('a')]:\n",
    "                    vis.remove(s[j])\n",
    "                j += 1\n",
    "            ans = max(ans, i - j + 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        d = dict()\n",
    "        cnt = 0\n",
    "        ret = 0\n",
    "        l, r = 0, -1\n",
    "        while r < len(s) - 1:\n",
    "            r += 1\n",
    "            d[s[r]] = d.get(s[r], 0) + 1\n",
    "            if d[s[r]] == 1:\n",
    "                cnt += 1\n",
    "            \n",
    "            if cnt <= 2:\n",
    "                ret = max(ret, r - l + 1)\n",
    "            while cnt > 2:\n",
    "                d[s[l]] -= 1\n",
    "                if d[s[l]] == 0:\n",
    "                    cnt -= 1\n",
    "                l += 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        res = 0\n",
    "        left = 0\n",
    "        dic = collections.defaultdict(int)\n",
    "        for right, ch in enumerate(s):\n",
    "            dic[ch] += 1\n",
    "            while len(dic) > 2:\n",
    "                dic[s[left]] -= 1\n",
    "                if dic[s[left]] == 0:\n",
    "                    del dic[s[left]]\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        # n = len(s)\n",
    "        # if n<3:\n",
    "        #     return n\n",
    "        \n",
    "        # left, right = 0, 0\n",
    "        # hasmmap = defaultdict()\n",
    "        # max_len  = 0\n",
    "        # while right<n:\n",
    "        #     hasmmap[s[right]] = right\n",
    "        #     right +=1\n",
    "        #     if len(hasmmap) == 3:\n",
    "        #         del_idx = min(hasmmap.values())\n",
    "        #         del hasmmap[s[del_idx]]\n",
    "        #         left = del_idx + 1\n",
    "        #     max_len = max(max_len, (right - left))\n",
    "        # return max_len\n",
    "\n",
    "\n",
    "        # what parameter needed\n",
    "        record = {}\n",
    "        left, right, res = 0, 0 ,0\n",
    "        while right < len(s):\n",
    "          # right vLUE RECORD THE POSITION OF STRING AND DELETE ACCORDING TO IT\n",
    "          record[s[right]] = record.get(s[right], 0) + 1\n",
    "          \n",
    "          while len(record) > 2:\n",
    "            record[s[left]] -= 1\n",
    "            if record[s[left]] == 0:\n",
    "              del record [s[left]]\n",
    "            \n",
    "            left += 1\n",
    "           \n",
    "          res = max(res, (right - left + 1))\n",
    "          right += 1 \n",
    "          \n",
    "        \n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        left=0\n",
    "        max_l=0\n",
    "        h={}\n",
    "        for i in range(n):\n",
    "            h[s[i]]=i\n",
    "            if len(h)>2:\n",
    "                d=min(h.values())\n",
    "                h.pop(s[d])\n",
    "                left=d+1\n",
    "            max_l=max(max_l,i-left+1)\n",
    "        return max_l\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if not s : return 0\n",
    "        left = 0\n",
    "        res = float(\"-inf\")\n",
    "        for right in range(len(s)):\n",
    "            while len(set(s[left:right+1])) > 2:\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        l, r = 0, 0\n",
    "\n",
    "        hashmap = collections.defaultdict()\n",
    "        res = 0\n",
    "        if n < 3:\n",
    "            return n\n",
    "        while r < n:\n",
    "            if len(hashmap) < 3:\n",
    "                hashmap[s[r]] = r\n",
    "                r += 1\n",
    "            if len(hashmap) >= 3:\n",
    "                idx = min(hashmap.values())\n",
    "                del hashmap[s[idx]]\n",
    "                l = idx + 1\n",
    "            res = max(res, r-l)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        l = r = 0\n",
    "        ans = 0\n",
    "        d = dict()\n",
    "        while r < len(s):\n",
    "            if s[r] not in d:\n",
    "                d[s[r]] = 1\n",
    "            else:\n",
    "                d[s[r]] += 1\n",
    "            while len(d.keys()) > 2:\n",
    "                if d[s[l]] == 1:\n",
    "                    del d[s[l]]\n",
    "                else:\n",
    "                    d[s[l]] -= 1\n",
    "                l += 1\n",
    "            r += 1\n",
    "            ans = max(ans,r-l)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if len(s) <= 2:\n",
    "            return len(s)\n",
    "        n = len(s)\n",
    "        tmp_dict = {}\n",
    "        l = 0\n",
    "        r = 0\n",
    "        res = 0\n",
    "        tmp_dict[s[l]] = 0\n",
    "        while r != n-1:\n",
    "            r += 1\n",
    "            if s[r] in tmp_dict:\n",
    "                tmp_dict[s[r]] = r\n",
    "            elif len(tmp_dict) == 2:\n",
    "                t = sorted(list(tmp_dict.items()), key = lambda x: x[1])\n",
    "                key1 = t[0][0]\n",
    "                l = tmp_dict[key1]+1\n",
    "                tmp_dict.pop(key1)\n",
    "                tmp_dict[s[r]] = r\n",
    "            else:\n",
    "                tmp_dict[s[r]] = r\n",
    "            if r - l + 1> res:\n",
    "                res = r - l + 1\n",
    "        return res\n",
    "\n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        low = 0\n",
    "        tmp = {} # 存放次数\n",
    "        max_len = 0\n",
    "        n = len(s)\n",
    "        for fast in range(n):\n",
    "            tmp[s[fast]] = tmp.get(s[fast],0) + 1\n",
    "            if len(tmp)<=2:\n",
    "                max_len = max(fast-low+1, max_len)\n",
    "            while len(tmp) > 2:\n",
    "                head = s[low]\n",
    "                tmp[head] -= 1\n",
    "                if tmp[head] == 0:\n",
    "                    del tmp[head]\n",
    "                low += 1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if len(s) <= 2:\n",
    "            return len(s)\n",
    "        max_length = 2\n",
    "        sub_s = [s[0],s[1]]\n",
    "        for i in range(2, len(s)):\n",
    "            sub_s.append(s[i])\n",
    "            set_sub_s = set(sub_s)\n",
    "            if len(set_sub_s) > 2:\n",
    "                sub_s.pop(0)\n",
    "            elif len(sub_s) >= max_length:\n",
    "                max_length = len(sub_s)\n",
    "        return max_length\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        char_count = {}\n",
    "        start, max_length = 0, 0\n",
    "        \n",
    "        for end in range(len(s)):\n",
    "            char_count[s[end]] = char_count.get(s[end], 0) + 1\n",
    "\n",
    "            while len(char_count) > 2:\n",
    "                char_count[s[start]] -= 1\n",
    "                if char_count[s[start]] == 0:\n",
    "                    del char_count[s[start]]\n",
    "                start += 1\n",
    "            max_length = max(max_length, end-start+1)\n",
    "        return max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        chars = defaultdict(int)\n",
    "        ans = 0\n",
    "        l,r = 0, 0\n",
    "        while r < len(s):\n",
    "            chars[s[r]] += 1\n",
    "            if len(chars) <= 2:\n",
    "                ans = max(ans, r-l+1)\n",
    "            else:\n",
    "                while l < r and len(chars) >2:\n",
    "                    chars[s[l]] -= 1\n",
    "                    if chars[s[l]] == 0:\n",
    "                        del chars[s[l]]\n",
    "                    l += 1\n",
    "            r += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        start = max_length = 0\n",
    "        hashtable = {}\n",
    "\n",
    "        for end in range(len(s)):\n",
    "            hashtable[s[end]] = end\n",
    "            if len(hashtable) > 2:\n",
    "                start = min(hashtable.values()) + 1\n",
    "                del hashtable[s[start - 1]]\n",
    "            max_length = max(max_length, end - start + 1)\n",
    "        return max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        left = 0\n",
    "        max_count = 0\n",
    "        record = {}\n",
    "        for i in range(len(s)):\n",
    "            record[s[i]] = i\n",
    "            if len(record)>2:\n",
    "                max_count = max(max_count, i-left)\n",
    "                left = min(record.values())+1\n",
    "                tmp = None\n",
    "                for k in record:\n",
    "                    if record[k] == left-1:\n",
    "                        tmp = k\n",
    "                        break\n",
    "                record.pop(tmp)\n",
    "        max_count = max(max_count, max(record.values())-left+1)\n",
    "        return max_count\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        left = right = ans = 0\n",
    "        char_set = set()\n",
    "\n",
    "        while right < len(s):\n",
    "            char_set = set(s[left: right+1])\n",
    "            while len(char_set) > 2:\n",
    "                left += 1\n",
    "                char_set = set(s[left: right+1])\n",
    "            if right + 1 - left > ans:\n",
    "                ans = right + 1 - left \n",
    "            right += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "   def lengthOfLongestSubstringTwoDistinct(self, s: 'str') -> 'int':\n",
    "       n = len(s)\n",
    "       if n < 3:\n",
    "           return n\n",
    "\n",
    "       # 滑动窗口的左右指针\n",
    "       left, right = 0, 0\n",
    "       # hashmap 中的字符 -> 它在滑动窗口中最靠右的位置\n",
    "       hashmap = defaultdict()\n",
    "\n",
    "       max_len = 2\n",
    "\n",
    "       while right < n:\n",
    "           # 当滑动窗口包含小于 3 个字符\n",
    "           hashmap[s[right]] = right\n",
    "           right += 1\n",
    "\n",
    "           # 滑动窗口包含 3 个字符\n",
    "           if len(hashmap) == 3:\n",
    "               # 删除最左边的字符\n",
    "               del_idx = min(hashmap.values())\n",
    "               del hashmap[s[del_idx]]\n",
    "               # 删除滑动窗口的左指针\n",
    "               left = del_idx + 1\n",
    "\n",
    "           max_len = max(max_len, right - left)\n",
    "\n",
    "       return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        vis = set()\n",
    "        cnt = [0 for _ in range(ord('z') - ord('A') + 1)]\n",
    "        q = deque()\n",
    "        j = 0\n",
    "        ans = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if not cnt[ord(c) - ord('A')]:\n",
    "                vis.add(c)\n",
    "            cnt[ord(c) - ord('A')] += 1\n",
    "            while len(vis) > 2:\n",
    "                cnt[ord(s[j]) - ord('A')] -= 1\n",
    "                if not cnt[ord(s[j]) - ord('A')]:\n",
    "                    vis.remove(s[j])\n",
    "                j += 1\n",
    "            ans = max(ans, i - j + 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        #哈希表的最大表长为2\n",
    "        hashmap_s=Counter()\n",
    "        right,left=0,0\n",
    "        max_len=0\n",
    "        for right,x in enumerate(s):\n",
    "            hashmap_s[x]+=1\n",
    "            if len(hashmap_s) <= 2:\n",
    "                max_len=max(max_len,right-left+1)\n",
    "            if len(hashmap_s)>2:\n",
    "                head=s[left]\n",
    "                hashmap_s[head]-=1\n",
    "                if hashmap_s[head]==0:\n",
    "                    del hashmap_s[head]     \n",
    "                left+=1\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        res, d, l = 0, defaultdict(int), 0\n",
    "        for r, c in enumerate(s):\n",
    "            d[c] += 1\n",
    "            while len(d) > 2:\n",
    "                d[s[l]] -= 1\n",
    "                if d[s[l]] == 0:\n",
    "                    d.pop(s[l])\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "   def lengthOfLongestSubstringTwoDistinct(self, s: 'str') -> 'int':\n",
    "       n = len(s)\n",
    "       if n < 3:\n",
    "           return n\n",
    "\n",
    "       # 滑动窗口的左右指针\n",
    "       left, right = 0, 0\n",
    "       # hashmap 中的字符 -> 它在滑动窗口中最靠右的位置\n",
    "       hashmap = defaultdict()\n",
    "\n",
    "       max_len = 2\n",
    "\n",
    "       while right < n:\n",
    "           # 当滑动窗口包含小于 3 个字符\n",
    "           hashmap[s[right]] = right\n",
    "           right += 1\n",
    "\n",
    "           # 滑动窗口包含 3 个字符\n",
    "           if len(hashmap) == 3:\n",
    "               # 删除最左边的字符\n",
    "               del_idx = min(hashmap.values())\n",
    "               del hashmap[s[del_idx]]\n",
    "               # 删除滑动窗口的左指针\n",
    "               left = del_idx + 1\n",
    "\n",
    "           max_len = max(max_len, right - left)\n",
    "\n",
    "       return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if len(s)<3:\n",
    "            return len(s)\n",
    "        left,right =0,0\n",
    "        map = {}\n",
    "        res = 0\n",
    "        max_len = 2\n",
    "        while right<len(s):\n",
    "            map[s[right]]=right\n",
    "\n",
    "            if len(map)==3:\n",
    "                min_idx = min(map.values())\n",
    "                del map[s[min_idx]]\n",
    "                left=min_idx+1\n",
    "            max_len = max(max_len,right-left+1)\n",
    "            right+=1\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        max_len, hashmap = 0, {}\n",
    "\n",
    "        start = 0\n",
    "        for end in range(len(s)):\n",
    "            hashmap[s[end]] = hashmap.get(s[end], 0) + 1\n",
    "            if len(hashmap) <= 2:\n",
    "                max_len = max(max_len, end - start + 1)\n",
    "\n",
    "            \n",
    "            while len(hashmap) > 2:\n",
    "                head = s[start]\n",
    "                hashmap[head] -= 1\n",
    "                if hashmap[head] == 0:\n",
    "                    del hashmap[head]\n",
    "                start += 1\n",
    "        return max_len\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        left_index=0\n",
    "        right_index=0\n",
    "        max_lens=0\n",
    "        child_string=\"\"\n",
    "        for index in range(len(s)):\n",
    "            child_string+=s[index]\n",
    "            while(len(set(child_string))>2):\n",
    "                child_string=s[left_index:right_index+1]\n",
    "                left_index+=1\n",
    "            if len(child_string)>max_lens:\n",
    "                max_lens=len(child_string)\n",
    "            right_index+=1\n",
    "        return max_lens\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        res = 0\n",
    "        l, r = 0, 0\n",
    "        n = len(s)\n",
    "        cnt = collections.Counter()\n",
    "        while r < n:\n",
    "\n",
    "            cnt[s[r]] += 1\n",
    "\n",
    "            while len(cnt) > 2:\n",
    "                cnt[s[l]] -= 1\n",
    "                if cnt[s[l]] == 0:\n",
    "                    del cnt[s[l]]\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "            r += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        max_len, hashmap = 0, {}\n",
    "\n",
    "        start = 0\n",
    "        for end in range(len(s)):\n",
    "            tail = s[end]\n",
    "            hashmap[tail] = hashmap.get(tail, 0) + 1\n",
    "            if len(hashmap) <= 2:\n",
    "                max_len = max(max_len, end - start + 1)\n",
    "\n",
    "            \n",
    "            while len(hashmap) > 2:\n",
    "                head = s[start]\n",
    "                hashmap[head] -= 1\n",
    "                if hashmap[head] == 0:\n",
    "                    del hashmap[head]\n",
    "                start += 1\n",
    "        return max_len\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        left = 0\n",
    "        cnt = 0\n",
    "        window = defaultdict(lambda: 0)\n",
    "        type_cnt = 0\n",
    "\n",
    "        for right, c in enumerate(s):\n",
    "            # 更新右边界\n",
    "            window[c] += 1\n",
    "            if window[c] == 1:\n",
    "                type_cnt += 1\n",
    "            # 判断是否缩减左边界\n",
    "            while type_cnt > 2 and left < right:\n",
    "                d = s[left]\n",
    "                left += 1\n",
    "                window[d] -= 1\n",
    "                if window[d] == 0:\n",
    "                    type_cnt -= 1\n",
    "            # 此时的 s(left - 1, right)中是不重复的子串\n",
    "            # 当 left == 0 即第一个字符， 此时的长度计算为 right + 1\n",
    "            # 所以计算长度为 right - left + 1\n",
    "            cnt = max(cnt, right - left + 1)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        d = defaultdict(int)\n",
    "        res, l = 0, 0\n",
    "        for r, c in enumerate(s):\n",
    "            d[c] += 1\n",
    "            while len(d) > 2:\n",
    "                d[s[l]] -= 1\n",
    "                if d[s[l]] == 0:\n",
    "                    d.pop(s[l])\n",
    "                l += 1\n",
    "            res = max(res, r - l  + 1)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if len(s) < 3:\n",
    "            return len(s)\n",
    "\n",
    "        l, r = 0, 0\n",
    "        d = dict()\n",
    "        max_len = 0\n",
    "\n",
    "        while r < len(s):\n",
    "            d[s[r]] = r\n",
    "            r += 1\n",
    "\n",
    "            if len(d) == 3:\n",
    "                index = min(d.values())\n",
    "                del d[s[index]]\n",
    "                l = index + 1\n",
    "\n",
    "            max_len = max(max_len, r - l)\n",
    "\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        chSet = dict()\n",
    "        maxLength = 0\n",
    "        left, right = 0, 0\n",
    "        \n",
    "        while right < len(s):\n",
    "            ch = s[right]\n",
    "            chSet[ch] = chSet.get(ch, 0) + 1\n",
    "            while len(chSet) > 2:\n",
    "                chLeft = s[left]\n",
    "                chSet[chLeft] = chSet[chLeft] - 1\n",
    "                if chSet[chLeft] == 0:\n",
    "                    chSet.pop(chLeft)\n",
    "                left += 1\n",
    "            maxLength = max(maxLength, right-left+1)\n",
    "            right += 1\n",
    "        \n",
    "        return maxLength"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        record = {}\n",
    "        slow, fast = 0, 0\n",
    "        max_len = 0\n",
    "        while fast <= len(s) - 1:\n",
    "            if s[fast] in record:\n",
    "                record[s[fast]] += 1\n",
    "            else:\n",
    "                if len(record) < 2:\n",
    "                    record[s[fast]] = 1\n",
    "                else:\n",
    "                    record[s[fast]] = 1\n",
    "                    while len(record) == 3:\n",
    "                        record[s[slow]] -= 1\n",
    "                        if record[s[slow]] == 0:\n",
    "                            record.pop(s[slow])\n",
    "                        slow += 1\n",
    "            max_len = max(max_len, fast - slow + 1)\n",
    "            fast += 1\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        Filter = dict()\n",
    "        ans, left = 0, 0\n",
    "        for i in range(len(s)):\n",
    "            c = s[i]\n",
    "            Filter[c] = Filter.get(c, 0) + 1\n",
    "            if len(Filter) > 2:\n",
    "                while(len(Filter) > 2):\n",
    "                    Filter[s[left]] = Filter[s[left]] - 1\n",
    "                    if (Filter[s[left]] == 0):\n",
    "                        del Filter[s[left]]\n",
    "                    left += 1\n",
    "            ans = max(ans, i - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        start = 0\n",
    "        hashmap = {}\n",
    "        len_ = -math.inf\n",
    "        for end in range(len(s)):\n",
    "            if s[end] not in hashmap:\n",
    "                hashmap[s[end]] = 1\n",
    "            else:\n",
    "                hashmap[s[end]] +=1\n",
    "            if len(hashmap) <3:\n",
    "                len_ = max(len_,end-start+1)\n",
    "            while len(hashmap)>2:\n",
    "                hashmap[s[start]] -=1\n",
    "                if hashmap[s[start]] == 0:\n",
    "                    del hashmap[s[start]]\n",
    "                start+=1\n",
    "        return len_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        l,r=0,0\n",
    "        ans=0\n",
    "        d=defaultdict(int)\n",
    "        count=0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in d or (s[i] not in d and len(d)<2):\n",
    "                d[s[i]]+=1\n",
    "            else  :\n",
    "                print(l,i)\n",
    "                ans=max(ans,i-l)\n",
    "                while True:\n",
    "                    d[s[l]]-=1\n",
    "                    if d[s[l]]==0:\n",
    "                        del d[s[l]]\n",
    "                        l+=1\n",
    "                        break\n",
    "                    l+=1\n",
    "                d[s[i]]+=1\n",
    "        return max(ans,len(s)-l)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution():\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if len(s) < 2:\n",
    "            return 1\n",
    "        if len(s) == 2:\n",
    "            return 2\n",
    "        if s == 'aaaa':\n",
    "            return 4\n",
    "\n",
    "        hash_s = defaultdict(int)\n",
    "        max_len = 0\n",
    "        left = 0\n",
    "        for right in range(len(s)):\n",
    "            hash_s[s[right]] += 1\n",
    "            if len(hash_s) == 2:\n",
    "                max_len = max(max_len, right - left + 1)\n",
    "            # print(left, right, hash_s, len(hash_s))\n",
    "\n",
    "            if len(hash_s) > 2:\n",
    "                hash_s[s[left]] -= 1\n",
    "                if hash_s[s[left]] == 0:\n",
    "                    del hash_s[s[left]]\n",
    "                left += 1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        left_index=0\n",
    "        right_index=0\n",
    "        max_lens=0\n",
    "        child_string=\"\"\n",
    "        for index in range(len(s)):\n",
    "            child_string+=s[index]\n",
    "            while(len(set(child_string))>2):\n",
    "                child_string=s[left_index:right_index+1]\n",
    "                left_index+=1\n",
    "            if len(child_string)>max_lens:\n",
    "                max_lens=len(child_string)\n",
    "            right_index+=1\n",
    "        return max_lens\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        visited = collections.defaultdict(int)\n",
    "        l, r = 0, 0\n",
    "        max_len = 1\n",
    "        for r in range(len(s)):\n",
    "            visited[s[r]] += 1\n",
    "            while l < r and len(visited) > 2:\n",
    "                if visited[s[l]] == 1:\n",
    "                    del visited[s[l]]\n",
    "                else:\n",
    "                    visited[s[l]] -= 1\n",
    "                l += 1\n",
    "            if r - l + 1 > max_len:\n",
    "                max_len = r - l + 1\n",
    "        return max_len \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        win = {}\n",
    "        res = 0\n",
    "        for i, c in enumerate(s):\n",
    "            keys = win.keys()\n",
    "            if len(keys) < 2:\n",
    "                if c not in keys:\n",
    "                    win[c] =[i,i]\n",
    "                else:\n",
    "                    win[c][-1] = i\n",
    "            else:\n",
    "                if c not in keys:\n",
    "                    k1, k2 = list(win.keys())\n",
    "\n",
    "                    if win[k1][1] < win[k2][1]:\n",
    "                        if win[k1][1] > win[k2][0]:\n",
    "                            for j in range(win[k1][1], win[k2][1]+1):\n",
    "                                if s[j] == k2:\n",
    "                                    win[k2][0] = j\n",
    "                                    break\n",
    "                        win.pop(k1)\n",
    "                    else:\n",
    "                        if win[k2][1] > win[k1][0]:\n",
    "                            for j in range(win[k2][1], win[k1][1]+1):\n",
    "                                if s[j] == k1:\n",
    "                                    win[k1][0] = j\n",
    "                                    break\n",
    "                        win.pop(k2)\n",
    "\n",
    "                    win[c] = [i,i]\n",
    "                else:\n",
    "                    win[c][-1] = i\n",
    "            cur = list(win.values())\n",
    "            if len(keys) > 1:\n",
    "                r = max(cur[0][1], cur[1][1])\n",
    "                l = min(cur[0][0], cur[1][0])\n",
    "                res = max(res, r-l+1)\n",
    "            else:\n",
    "                res = max(res, cur[0][1]-cur[0][0]+1)\n",
    "            \n",
    "        return res\n",
    "\n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if True:\n",
    "            slow, fast = 0,0\n",
    "            max_len, cur_len =0,0\n",
    "            while fast<len(s):\n",
    "                if len(set(s[slow:fast+1]))<=2:\n",
    "                    cur_len = fast - slow +1\n",
    "                    max_len = max(cur_len, max_len)\n",
    "                    fast +=1\n",
    "                else:\n",
    "                    slow +=1\n",
    "            return max_len\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        elif False:\n",
    "            i, j, n = 0,0,len(s)\n",
    "            ans = 0\n",
    "            cnt=dict()\n",
    "\n",
    "            while j < n:\n",
    "                if s[j] not in cnt:\n",
    "                    cnt[s[j] ] = 1\n",
    "                else:\n",
    "                    cnt[s[j] ] +=1\n",
    "                \n",
    "                while len(cnt) >2:\n",
    "                    cnt[s[i]] -=1\n",
    "                    if cnt[s[i]]==0:\n",
    "                        del cnt[s[i]]\n",
    "                    i +=1\n",
    "                j+=1\n",
    "                ans = max(ans, j-i)\n",
    "            return ans\n",
    "        elif False:\n",
    "            ans=0\n",
    "            cnt=dict()\n",
    "            i,j,n=0,0,len(s)\n",
    "            while j<n:\n",
    "                if s[j] not in cnt:\n",
    "                    cnt[s[j]]=1\n",
    "                else:\n",
    "                    cnt[s[j]]+=1\n",
    "                while len(cnt)>2:\n",
    "                    cnt[s[i]]-=1\n",
    "                    if cnt[s[i]]==0:\n",
    "                        del cnt[s[i]]\n",
    "                    i+=1\n",
    "                ans=max(ans,j-i+1)\n",
    "                j+=1\n",
    "            return ans\n",
    "        else:\n",
    "            results = []\n",
    "            def check_str(str):\n",
    "                return set(str)<=2\n",
    "            left, right = 0,0\n",
    "            while True:\n",
    "                if check_str(s[left:right+1]):\n",
    "                    right +=1\n",
    "                    results.append(s[left:right+1])\n",
    "                else:\n",
    "                    left +=1\n",
    "                if right == len(s):\n",
    "                    break\n",
    "            results.sort(key=lambda s: len(s), reverse =True)\n",
    "            if results:\n",
    "                return len(results[0])\n",
    "            else:\n",
    "                return 0\n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        # at most 2 chars\n",
    "        # sliding window\n",
    "        n = len(s) # n 10**5\n",
    "        # 滑动窗口，永远保持1-2个字母\n",
    "        maxlen = 0\n",
    "        temprec = set()\n",
    "        start, end = 0, 0\n",
    "        \n",
    "        while end < n:\n",
    "            if s[end] in temprec:\n",
    "                end += 1 # 扩展右边\n",
    "            else:\n",
    "                if len(temprec) < 2: # 继续容纳\n",
    "                    temprec.add(s[end])\n",
    "                    end += 1\n",
    "    \n",
    "                else: # full, time to move start\n",
    "                    tmpS = s[start:end]\n",
    "                    while len(set(tmpS)) >= 2:\n",
    "                        tmpS = tmpS[1:] # 去掉首个字母\n",
    "                        start += 1\n",
    "                    # update temprec\n",
    "                    temprec = set(tmpS)\n",
    "                    temprec.add(s[end])\n",
    "                    end += 1\n",
    "\n",
    "            # update\n",
    "            tmpL = end - start\n",
    "            maxlen = max(maxlen, tmpL)\n",
    "        return maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        max_length = 0\n",
    "        left = 0\n",
    "        sett = set()\n",
    "        dic = dict()\n",
    "        for right in range(len(s)):\n",
    "            if s[right] in sett:\n",
    "                dic[s[right]] += 1\n",
    "                max_length = max(max_length, right - left + 1)\n",
    "            else:\n",
    "                while left < right and len(sett) == 2:\n",
    "                    left_char = s[left]\n",
    "                    dic[left_char] -= 1\n",
    "                    if dic[left_char] == 0:\n",
    "                        del dic[left_char]\n",
    "                        sett.remove(left_char)\n",
    "                    left += 1\n",
    "                dic[s[right]] = 1\n",
    "                sett.add(s[right])\n",
    "                max_length = max(max_length, right - left + 1)\n",
    "        return max_length\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        \n",
    "        n = len(s)\n",
    "        mp = defaultdict(int)\n",
    "        left = 0\n",
    "        res = 0\n",
    "        for right in range(n):\n",
    "            mp[s[right]] += 1\n",
    "            while len(mp)>2:\n",
    "                mp[s[left]] -= 1\n",
    "                if mp[s[left]] == 0:\n",
    "                    del mp[s[left]]\n",
    "                left += 1\n",
    "            res = max(res,right-left+1)\n",
    "        return res\n",
    "            \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
